1. Field of the Invention
The present invention relates to the field of error correction, intended for reduction of rate of occurrence of error in the path of transmission from a device such as an optical disk device, opto-magnetic disk device, and so forth.
More particularly, the invention relates to an error correction circuit for use in a digital electronic device such as a digital audio device, particularly a flag strategy setting circuit which is typically a BCH (Bose-Chaudhuri-Hocquenghem) encoding and decoding circuit for use in the error correction circuit.
Still more particularly, the invention is concerned with a syndrome creating circuit incorporated in the BCH encoding and decoding circuit, particularly to an unknown-exponent/vector conversion circuit, multiplication circuit and division circuit on a Galois function. The term, Galois function, in this specification is used to mean a set of a definite number of unknowns which can be processed by addition, subtraction, multiplication and division and usually expressed as GF (q), where q represents the number of unknowns.
2. Related Background Art
Hitherto, error correction apparatus of the type described has been generally designed to operate in response to an error correction code of a predetermined format having factors such as the length of error correction code, correction capacity and interleave. Thus, the known error correction apparatus could not operate when the correction code of a different format is applied and when a plurality of blocks of correction codes of various formats are supplied serially.
Optical disks and opto-magnetic disks are usually kept under sector administration. The sector contains not only ordinary data, but also address data. Protection of these two types of data is a matter of great significance. Conventionally, error correction codes such as Reed Solomon codes have been used as protection means for protecting the ordinary data portion, while error detection codes such as CRC (Cyclic Redundancy Check) codes have been used as means for protecting the address data. An erroneous recognition of the address data will lead to an error of the whole sector. Therefore, in the conventional systems, a greater importance has been given to the detection accuracy than to the correction performance insofar as the address data is concerned. Thus, any error in the address data has been corrected through an over-writing or re-try. There are some types of recording medium which enables the address data to be corrected through re-try, but not through overwriting. An example of such a type of recording medium is an opto-magnetic disk. In the correction of address data in such a recording medium, it is necessary that the disk is rotated three times: first rotation for erasure, second rotation for writing and third rotation for check, each rotation requiring detection of address. Consequently, the number of the re-try cycles is increased, resulting in a longer delay time, particularly in the medium having a greater rate of occurrence of error. It would be possible to use an error correction code for the purpose of correction of address data. In general, however, an error correction device requires a much more complicated construction than the error detecting device. When the correction of address data is to be conducted by means of a correction code, it is necessary to use a pair of error correction devices: namely, one for correction of address data and one for correction of ordinary data.
THE THEORY OF ERROR CORRECTING CODES, written by F. J. MacWiliam and N. J. A. Sloan, published in 1978 by North Holland Publishing Company, U.S.A., proposes CIRC (Cross-Interleaved Reed Solomon Code), particularly two-staged decoding having 2-symbol error correction facility. Typical examples of the strategy used in this two-staged decoding are as follows, where C1 decoder and C2 decoder mean the decoders which conduct decoding earlier and later, respectively.
______________________________________ (1) Simple strategy C1 decoder 1 symbol error correction 3 symbol error detection C2 decoder 1 symbol error correction 3 symbol error detection (2) Super strategy C1 decoder 2 symbol error correction (Flag is set up in case of 2 symbol error correction) C2 decoder 2 symbol error correction ______________________________________
In the case of a digital audio equipment, any detection error causes a click noise and, hence, is critical. Any error which cannot be corrected, however, can be compensated for by interpolation to such an extent that it does not substantially impair the audio effect, provided that the error is detected. It is therefore necessary to maximize the error detection capacity at the cost of reduced error correction capacity, as in the simple strategy (1) shown above. When the compensation by, for example, the interpolation is not effective, 2 symbol error correction is performed by the C1 decoder as in the case of the super strategy (2) mentioned above. In this case, a flag is set up to also enhance the error detection capacity, thereby to reduce the rate of error detection failure.
It is thus possible to optimize the format for error detection by selectively changing the strategy, even when the format has an identical construction, both in vertical and horizontal directions.
A description will be made hereinunder as to a super strategy (2) on an assumption that C1 decoder (32, 28) and C2 decoder (28, 24) are used.
i) C1 decoder
The following process is conducted in accordance with the result of judgment of received syndrome Sc1.
______________________________________ (a) Sc1 = "0" .fwdarw. Correction not conducted ; Fc1 = 0 (b) Sc1 = "1" .fwdarw. 1 symbol error corrected ; Fc1 = 0 (c) Sc1 = "2" .fwdarw. 2 symbol error corrected ; Fc1 = 1 (d) Sc1 .gtoreq. "3" .fwdarw. Correction not conducted ; Fc1 = 1 where, "n": n-symbol error syndrome Fc1: Flag data created in C1 decoder and sent to C2 decoder Fc1 = 0 .fwdarw. No error Fc1 = 1 .fwdarw. Possibility of inclusion of any error ______________________________________
ii) C2 decoder
The following process is conducted in accordance with the result of judgment of received syndrome Sc2, and number and positions of flags Fc1from C1 decoder.
______________________________________ (a) Sc2 = "0" .fwdarw. Correction not conducted ; Fc2 = 0 (b) Sc2 = "1" .fwdarw. 1 symbol error corrected ; Fc2 = 0 (c) Sc2 = "2", Nc1 .ltoreq. 4, Lc1 = 2 .fwdarw. 2 symbol error corrected ; Fc2 = 0, Nc1 .ltoreq. 3, Lc1 = 1 or Nc1 .ltoreq. 2, Lc1 = 0 .fwdarw. Correction not conducted ; Fc2 = 1, Other cases .fwdarw. Correction not conducted ; Fc2 = Fc1 (d) Sc2 .gtoreq. "3", Nc1 .ltoreq. 2 .fwdarw. Correction not conducted Fc2 = 1 Other cases .fwdarw. Correction not conducted Fc2 = Fc1 ______________________________________
where,
Nc1: Number of flags Fc1 received by C2 decoder
Lc1: Number of flags Fc1 coincided with error location
Fc2: Flag created in C2 decoder
Fc2=0 .fwdarw.No error PA2 Fc2=1 .fwdarw.All errors PA2 Fc2=Fc1.fwdarw.Flags created in C1 decoder are copied.
The above-described principle will be more readily understood from FIG. 2. It will be seen that the simple strategy is the strategy in which the C2 decoder has the same construction as the C1 decoder shown in FIG. 2(1).
Conventionally, once the flag strategy in each of the C1 and C2 decoders is set as described above, the thus set strategy is fixed and cannot be freely changed or adjusted.
It is also a conventional way to conduct the BCH encoding by means of a division circuit employing a creating polynomial and to conduct the decoding by means of circuits of the respective algorithms such as those according to Peterson's method or Berlekamp-Massey.
Thus, the conventional system employs different circuits for encoding and decoding. Attempts have been made to conduct encoding and decoding by making use of the same circuit in a multiplied manner in accordance with, for example, microprogramming. In such a case, however, it is necessary that a delicate difference be made between the encoding process and the decoding process. Therefore, when the encoding and decoding are to be conducted by means of the same circuitboard or chip, the number of circuits or the capacity of ROM is increased inevitably. This in turn causes the size of the device such as an optical disk device to be increased undesirably.
The syndrome creating circuit in conventional BCH encoding or decoding circuit produces the syndrome S as represented by the following formula (2), upon receipt of a word J which, as shown in the following formula (1), has a term of the code word I and a term of error E. ##EQU1##
Namely, in case of double error correction encoding, the syndrome S is created as the product of a check matrix H and the received word J, as shown by the formula (2). ##EQU2## where, n represents the code length, H represents the check matrix, J represents the code length, S represents the syndrome, I represents the code word, and E represents the error,
From the following formula (3), it will be understood that the thus obtained syndrome (3) is the product of the check matrix H and the error E. ##EQU3##
Normally, the syndrome creating circuit can be expressed as follows for each syndrome Si. ##EQU4##
Thus, the syndrome creating circuit on the Galois function GF(2q) can be constructed as shown in FIG. 3. The .alpha..sup.i circuit can be realized by stacking the .alpha. circuit of FIG. 4 in i stages, on condition of a primitive polynomial p(x)=X.sup.8 +X.sup.4 +X.sup.3 +X.sup.2 +1. Thus, the syndrome creating circuit for realizing S0 to S3 expressed by the formula (2) can be constructed as shown in FIG. 5. In FIG. 5, CK represents clock for each received word Ji, while CL represents the clear for each code length.
Obviously, the size of the construction shown in FIG. 5 becomes large as the number q or the number i becomes large. In addition, the arrangement shown in FIG. 5 is not suitable for use in the case when the syndromes S0 to S3 are interconnected and processed through a BUS line.
There are two types of ways of expression of the unknown of the Galois member: namely, expression in terms of vector and expression in terms of exponent. Representing a Galois function having q unknowns by GF(q), the unknown .alpha..sup.8 created on GF(2.sup.8) from the primitive polynominal p(x)=X.sup.8 +X.sup.4 +X.sup.3 +X.sup.2 +1 is expressed as follows. ##EQU5##
This vector expression shows the bit pattern. Division in terms of vector is complicated and difficult to conduct. Practically, therefore, conversion into exponential expression is conducted as follows. ##EQU6##
The VE (vector to exponent) conversion and EV (exponent to vector) conversion can be conducted utilizing a ROM.
When division is to be completed in the period of 1 (one) clock as shown in FIG. 6, it is necessary to employ 3 (three) ROMs. In contrast, when the division is conducted by employing one ROM for VE conversion and one ROM for EV conversion as shown in FIG. 7, the operation requires a period corresponding to two clocks: first clock period for latching b by means of a register and second clock period for adding a.
Similarly, when multiplication is to be completed in the period of 1 (one) clock as shown in FIG. 8, it is necessary to employ 3 (three) ROMs, whereas, when multiplication is conducted by employing one ROM for VE conversion and one ROM for EV conversion as shown in FIG. 9, the operation requires a period corresponding to two clocks: first clock period for latching a by means of a register and second clock period for adding b.
It would be possible to conduct division or multiplication of two unknowns expressed in term of vectors directly by a ROM constituting a VE or EV conversion circuit. In such a case, the ROM will be required to have an impractically large capacity, particularly when the number of unknowns is large.